\documentclass{beamer}

\usetheme{Warsaw}
\setbeamercovered{transparent}

\usepackage[portuges]{babel}
\usepackage[utf8]{inputenc}
\usepackage{ulem}
\usepackage{epsfig}

\newcommand{\eng}[1]{\textsl{#1}}
\newcommand{\cod}[1]{\texttt{#1}}

\title[MC-102 --- Aula 23]{MC-102 --- Aula 23\\
Listas Ligadas II}

\author{}

\institute{Instituto de Computação -- Unicamp}

\date{Primeiro Semestre de 2006}

\begin{document}

\begin{frame}[plain]
  \titlepage
\end{frame}

\begin{frame}
  \frametitle{Roteiro}
  \tableofcontents
\end{frame}

\section{Lista Ligada}

\begin{frame}
  \frametitle{Filas}
\centerline{\epsfig{figure=fila.eps, scale=0.75}}
  \begin{itemize}
  \item Estrutura de dados em que
    \begin{itemize}
    \item inserções são feitas no final e

    \item remoções são feitas no começo

    \end{itemize}
    \item Veja o código fila.c

  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Pilha}
\medskip
  \centerline{\epsfig{figure=lista1.eps, scale=0.75}}
  \begin{itemize}
  \item Estrutura de dados em que
    \begin{itemize}
    \item inserções são feitas no começo e
      
    \item remoções são feitas no começo

    \end{itemize}
  \item Como seria o código pilha.c?

  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Busca}
  \medskip
  \centerline{\epsfig{figure=lista1.eps, scale=0.75}}
  \begin{itemize}
  \item A lista deve ser percorrida, procurando-se o elemento desejado.
  \item A busca é interrompida quando:
    \begin{itemize}
    \item O elemento foi encontrado ou
      \begin{itemize}
      \item chegamos ao final da lista (lista não ordenada)
      \item encontramos um elemento maior que o desejado (lista ordenada)
      \end{itemize}
    \end{itemize}

  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Inserção ordenada}
\centerline{\epsfig{figure=insere_ordenado.eps, scale=0.75}}

\begin{itemize}
\item O valor de {\tt p} pode ser alterado caso a inserção ocorra
  no início da lista;

\item A inserção também pode ocorrer no meio ou no final da lista.
\end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Remoção}
  \medskip
  \centerline{\epsfig{figure=remocao_especifico.eps, scale=0.75}}
  \begin{itemize}
  \item Procura-se o elemento a ser removido
  \item Atualiza-se a lista, caso ele tenha sido encontrado
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Lista circular}
  \medskip
  \centerline{\epsfig{figure=circular.eps, scale=0.75}}
  \begin{itemize}
  \item O último elemento aponta para o primeiro.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Lista com nó cabeça}
  \medskip
  \centerline{\epsfig{figure=cabeca.eps, scale=0.75}}
  \begin{itemize}
  \item O primeiro nó não armazena elementos da lista, mas pode
    armazenar dados sobre a lista, como o número de nós da lista.

  \item Simplifica as implementações. Reescreva todas as operações de
    inserção e remoção e comprove!
    
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Lista duplamente ligada}
  \medskip
  \centerline{\epsfig{figure=dupla.eps, scale=0.75}}
  \begin{itemize}
  \item Cada nó tem um apontador para o próximo elemento e para o
    elemento anterior na lista
  \end{itemize}
\end{frame}

\end{document}
